// https://www.lintcode.com/problem/minimum-path-sum/

public class Solution {
    /**
     * @param grid: a list of lists of integers
     * @return: An integer, minimizes the sum of all numbers along its path
     */
    public int minPathSum(int[][] grid) {
        // write your code here
        int rows = grid.length, cols = grid[0].length;
        int[][] cache = new int[rows][];
        for (int i = 0; i < rows; ++i) {
            cache[i] = new int[cols];
            for (int j = 0; j < cols; ++j) {
                cache[i][j] = -1;
            }
        }
        cache[0][0] = grid[0][0];
        return minPathSum(grid, cache, rows - 1, cols - 1);
    }
    
    private int minPathSum(int[][] grid, int[][] cache, int row, int col) {
        if (cache[row][col] > -1) {
            return cache[row][col];
        }
        int left = 2147483647, up = 2147483647;
        if (row > 0) {
            up = minPathSum(grid, cache, row - 1, col);
        }
        if (col > 0) {
            left = minPathSum(grid, cache, row, col - 1);
        }
        int ret = grid[row][col] + Math.min(up, left);
        cache[row][col] = ret;
        return ret;
    }
}